package com.example.myapplication.Algorithm.StatisticalPrimes;

public class Sushu {

    ///质数就是合数
    public static void main(String[] args){
        System.out.println(bf(100));
        System.out.println(eratosthenes(100));
    }
    ///暴力算法(把每个数都算上)，遍历x*n次
    public static int bf(int n){
        int count = 0;
        ///遍历n次
        for(int i=2;i<n;i++){
            count += isPrime(i)?1:0;
        }
        return count;
    }
    //    private static boolean isPrime(int x) {
//       ///遍历x次
//        for(int i=2;i<x;i++){
//            if(x%i==0){
//               return false;
//            }
//        }
//        return true;
//    }
    private static boolean isPrime(int x) {
        ///遍历x次
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }

    ///素数 非素数（合数） 12 = 2*6 （2和6为12的因子）
    ///将二倍增，排除倍增的合数
    ///埃氏筛选算法-(i*i优化 4*4=>例如(2*3,3*2))
    public static int eratosthenes(int n){
        boolean[] isPrime = new boolean[n];
        int count = 0;
        for(int i=2;i<n;i++){
            if(!isPrime[i]){
                count++;
                for (int j=i*i;j<n;j=j+i){
                    ///J是合数的标记位
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }

}
